package training;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_6_12_Training {
    //买卖股票的最佳时机 IV
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] fp = new int[n][k+1];
        int[][] dp = new int[n][k+1];
        for (int i = 1; i <= k; i++) {
            dp[0][i] = -0x3f3f3f3f;
            fp[0][i] = -0x3f3f3f3f;
        }
        fp[0][0] = -prices[0];
        dp[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                fp[i][j] = Math.max(fp[i][j],dp[i-1][j]-prices[i]);
                dp[i][j] = dp[i-1][j];
                if(j>=1){
                    dp[i][j] = Math.max(dp[i][j],fp[i-1][j-1]+prices[i]);
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i <= k; i++) {
            max = Math.max(max,dp[n-1][i]);
        }
        return max;
    }

    //按摩师
    public int massage(int[] nums) {
        int n = nums.length;
        if(n<=2){
            if(n==0){
                return 0;
            }else if(n==1){
                return nums[0];
            }else return Math.max(nums[1],nums[0]);
        }
        int[] fp = new int[n];
        int[] dp = new int[n];
        fp[0] = nums[0];
        fp[1] = nums[0];
        dp[1] = nums[1];
        for (int i = 2; i < n; i++) {
            fp[i] = Math.max(fp[i-1],dp[i-2]+nums[i]);
            dp[i] = Math.max(dp[i-1],fp[i-2]+nums[i]);
        }
        return Math.max(dp[n-1],fp[n-1]);
    }

    //地下城勇士
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length;
        int m = dungeon[0].length;
        int[][] dp = new int[n+1][m+1];
        int min = 0x3f3f3f3f;
        Arrays.fill(dp[0],-0x3f3f3f3f);
        dp[0][1] = 0;
        for (int i = 0; i <= n; i++) {
            dp[i][0] = -0x3f3f3f3f;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i-1][j]+dungeon[i-1][j-1],dp[i][j-1]+dungeon[i-1][j-1]);
                min = Math.min(min,dp[i][j]);
            }
        }
        return  1-min;
    }
}
